<?php
use WDB\GTO;

require 'loader.php';
require 'nette.min.php';
Nette\Diagnostics\Debugger::enable();
Nette\Diagnostics\Debugger::$strictMode = TRUE;

class GrammarCompiler extends WDB\BaseObject
{
    private $rules = array();
    private $rawRules = array();
    private $parsingTable = array();
    private $lambdaRules = array();
    private $terminals = array();
    private $nonTerminals = array();
    private $aliases = array();
    
    public static function compile($str)
    {
        $g = new self($str);
        $g->parseRules();
        echo '<style>table{border-collapse:collapse};td,th{border:1px solid #666;}</style><h3>Rules:</h3><p>';
        foreach ($g->rules as $id=>$rule)
        {
            echo "$id: {$rule->nonTerminal} -> ";
            if ($rule->rewriteTo)
            {
                echo implode(' ', $rule->rewriteTo);
            }
            else
            {
                echo "&#955;";
            }
            echo "<br>\n";
        }
        echo '</p><h3>Aliases:</h3><p>';
        foreach ($g->aliases as $alias=>$canonical)
        {
            echo "$alias -> $canonical<br>\n";
        }
        echo '</p>';
        $g->buildParsingTable();
        $g->checkWrongLambda();
        echo '<h3>Parsing table:</h3><table><tr><th>&nbsp;</th>';
        foreach ($g->terminals as $terminal)
        {
            echo "<th>$terminal</th>";
        }
        echo '<th>&#955;</th></tr>';
        foreach ($g->parsingTable as $nterm=>$stackTops)
        {
            echo '<tr><th>'.$nterm.'</th>';
            foreach ($g->terminals as $terminal)
            {
                if (isset($stackTops[$terminal]))
                {
                    echo '<td>'.$stackTops[$terminal].'</td>';
                }
                else
                {
                    echo '<td style="color:#999">-</td>';
                }
            }
            if (isset($g->lambdaRules[$nterm]))
            {
                echo '<td>'.$g->lambdaRules[$nterm].'</td>';
            }
            else
            {
                echo '<td style="color:#999">-</td>';
            }
            echo '</tr>';
        }
        echo '</table>';
        return GTO\Grammar::create($g->rules, $g->parsingTable, $g->lambdaRules, $g->aliases);
    }
    
    /**
     * Check for A->*LM1..MnNO*, Where L->a*, L->lambda & M1..Mn->lambda & (M1->a* |..| Mn->a* | O->a*)
     * which is not LL(1) because it is not clear whether to use L->lambda or L->a*
     */
    private function checkWrongLambda()
    {
        foreach($this->rules as $id=>$rule)
        {
            $forbiddenTerminals = array();
            foreach ($rule->rewriteTo as $symbol)
            {
                $symbol = $this->resolveAlias($symbol);
                if ($this->isNonTerm($symbol) && isset($this->lambdaRules[$symbol]))
                {
                    $possibleTerminals = $this->compareTerminals($symbol, $forbiddenTerminals, $id);
                    $forbiddenTerminals = array_merge($forbiddenTerminals, $possibleTerminals);
                }
                elseif ($forbiddenTerminals)
                {
                    $this->compareTerminals($symbol, $forbiddenTerminals, $id);
                    $forbiddenTerminals = array();
                }
            }
        }
    }
    
    private function resolveAlias($symbol)
    {
        if (isset($this->aliases[$symbol])) return $this->aliases[$symbol];
        return $symbol;
    }
    
    private function compareTerminals($symbol, $forbiddenTerminals, $ruleId)
    {
        if ($this->isTerm($symbol))
        {
            $possibleTerminals = array($symbol);
        }
        else
        {
            $possibleTerminals = array_keys($this->parsingTable[$symbol]);
        }
        
        if ($its = array_intersect($possibleTerminals, $forbiddenTerminals))
        {
            echo '<p style="color:red;font-weight:bold;">Warning: not an LL(1) grammar, same terminals ('.implode(', ', $its).') possible in chain of lambda nonterminals at rule '.$ruleId.'</p>';
        }
        return $possibleTerminals;
    }
    
    private function isTerm($symbol)
    {
        return ctype_lower($symbol{0});
    }
    private function isNonTerm($symbol)
    {
        return !ctype_lower($symbol{0});
    }
    
    private function buildParsingTable()
    {
        $this->addLambdaRules(); //build lambdaRules array and add transitive rules: if A->BCD, B->lamda,C->lambda,D->lambda, then A->lambda
        
        $this->parsingTable = array();
        //find rules A->t... beginning with terminal and put to parsing table
        foreach ($this->rules as $id=>$rule)
        {
            $nt = $this->resolveAlias($rule->nonTerminal);
            if (count($rule->rewriteTo) == 0)
            {
                if (!isset($this->parsingTable[$nt])) $this->parsingTable[$nt] = array(); //just to be complete
            }
            elseif ($this->isTerm($term = $this->resolveAlias($rule->rewriteTo[0]))) //begins with terminal
            {
                if (!in_array($term, $this->terminals))
                {
                    $this->terminals[] = $term;
                }
                $this->addToParsingTable($nt, $term, $id);
            }
        }
        //iteratively find rules A->B and add (B,x)=>(A,x) to parsing table.
        do {
            $anythingNew = false;
            foreach ($this->rules as $id=>$rule)
            {
                if (count($rule->rewriteTo) > 0 && $this->isNonTerm($this->resolveAlias($rule->rewriteTo[0]))) //begins with nonterminal
                {
                    $nt = $this->resolveAlias($rule->rewriteTo[$i=0]);
                        //if first nonterminal in rewriteTo can be lambda-ized, the original
                        //nonterminal can also begin with the following symbol.
                        //i.e. A->BC, B->lambda, C->x   means that (A, x)=>A->BC
                    if ($rule->nonTerminal == 'ColumnIdentifierOrFunction')
                    {
                        $a__ = 0;
                    }
                    do
                    {
                        if (isset($this->parsingTable[$nt]))
                        {
                            foreach ($this->parsingTable[$nt] as $stackTop=>$dummy)
                            {
                                $anythingNew = $this->addToParsingTable($this->resolveAlias($rule->nonTerminal), $stackTop, $id) || $anythingNew;
                            }
                        }
                        if (isset($this->lambdaRules[$nt]) && isset($rule->rewriteTo[++$i])) //processed nonterminal can be lambdaized
                        {
                            if ($this->isTerm($this->resolveAlias($rule->rewriteTo[$i])))
                            {   //next is terminal
                                $anythingNew = $this->addToParsingTable($this->resolveAlias($rule->nonTerminal), $this->resolveAlias($rule->rewriteTo[$i]), $id) || $anythingNew;
                            }
                            else 
                            {   //next is nonterminal
                                $nt = $this->resolveAlias($rule->rewriteTo[$i]);
                                continue;
                            }
                        }
                        break;
                    } while (TRUE);
                }
            }
        } while ($anythingNew);
    }
    
    private function addToParsingTable($nt, $stackTop, $ruleId)
    {
        if (!isset($this->parsingTable[$nt])) $this->parsingTable[$nt] = array();
        if (isset($this->parsingTable[$nt][$stackTop]) && $this->parsingTable[$nt][$stackTop] !== $ruleId)
        {
            throw new Exception("Not an LL(1) grammar; ambiguous rules: ($nt, $stackTop) can be rewritten to rules $ruleId and {$this->parsingTable[$nt][$stackTop]}");
        }
        if (!isset($this->parsingTable[$nt][$stackTop]))
        {
            $this->parsingTable[$nt][$stackTop] = $ruleId;
            return true;
        }
        else
        {
            return false;
        }
    }
    
    private function parseRules()
    {
        do 
        {
            $r = $this->rawRules;
            $this->rawRules = array();
            foreach ($r as $rule)
            {
                 $this->rules[] = $this->fetchRule($rule);
            }
        }
        while (count($this->rawRules) > 0);
    }
    
    private function addLambdaRules()
    {
        foreach ($this->rules as $id=>$rule)
        {
            if (count($rule->rewriteTo) == 0)
            {
                $this->lambdaRules[$this->resolveAlias($rule->nonTerminal)] = $id;
            }
        }
        do {
            $anythingNew = false;
            foreach ($this->rules as $id=>$rule)
            {
                if (isset($this->lambdaRules[$this->resolveAlias($rule->nonTerminal)])) continue; //already added
                $isLambda = true;
                foreach ($rule->rewriteTo as $symbol)
                {
                    if (!isset($this->lambdaRules[$this->resolveAlias($symbol)]))
                    {
                        $isLambda = false;
                        break;
                    }
                }
                if ($isLambda)
                {
                    $this->lambdaRules[$this->resolveAlias($rule->nonTerminal)] = $id;
                    $anythingNew = true;
                }
            }
        } while ($anythingNew);
    }
    
    private function __construct($str)
    {
        $g = \NeonWheel::decode($str);
        foreach ($g as $nterm=>$rules)
        {
            $this->parseNontermRule($nterm,$rules);
        }
    }
    
    private function parseNontermRule($nterm, $rules)
    {
        if (!in_array($nterm, $this->nonTerminals)) $this->nonTerminals[] = $nterm;
        if (is_array($rules))
        {   //pole pravidel $nterm=>{$rules}
            foreach ($rules as $key=>$rule)
            {
                if (is_string($key))
                {
                    $this->rawRules[] = array($nterm, $key);
                    if ($rule !== TRUE)
                    {
                        $this->parseNontermRule($key, $rule);
                    }
                }
                else
                {
                    $this->rawRules[] = array($nterm, $rule);
                }
            }
        }
        else
        {   //pravidlo $nterm=>$rules
            $this->rawRules[] = array($nterm, $rules);
        }
    }
    
    private function fetchRule($rule)
    {
        $count = 0;
        $r = $rule[1];
        do {
            $r = preg_replace_callback('~(?:(?<nterm>[A-Z][A-Za-z0-9_]*)=)?\\[(?<rule>[^][]+)\\]~', array($this, 'replaceObligatory'), $r, -1, $count);
        } while ($count > 0);
        $r = preg_replace_callback('~(?<alias>[A-Za-z0-9_]+):(?<symbol>[A-Za-z0-9_]+)~', array($this, 'replaceAlias'), $r);
        return GTO\Rule::create($rule[0], preg_match('~^\\s*$~', $r) ? array() : preg_split('~\\s+~', trim($r)));
    }
    
    private function replaceObligatory($matches)
    {
        if ($matches['nterm'])
        {
            $nt = $matches['nterm'];
        }
        else
        {
            $nt = $this->newNonTerm();
        }
        $this->rawRules[] = array($nt, '');
        $this->rawRules[] = array($nt, $matches['rule']);
        return $nt;
    }
    
    private function replaceAlias($matches)
    {
        if (isset($this->aliases[$matches['alias']]))
        {
            throw new Exception("Duplicate alias: {$matches['alias']}. Aliases must be unique over whole grammar.");
        }
        if (isset($this->terminals[$matches['alias']]))
        {
            throw new Exception("Duplicate identifier for alias: {$matches['alias']} with a terminal identifier.");
        }
        if (isset($this->nonTerminals[$matches['alias']]))
        {
            throw new Exception("Duplicate identifier for alias: {$matches['alias']} with a nonterminal identifier.");
        }
        $this->aliases[$matches['alias']] = $matches['symbol'];
        return $matches['alias'];
    }
    
    private $ntid = 0;
    
    private function newNonTerm()
    {
        while (in_array('N_'.$this->ntid, $this->nonTerminals)) ++$this->ntid;
        $this->nonTerminals[] = 'N_'.$this->ntid;
        return 'N_'.$this->ntid;
    }
}

if (isset($_GET['from'])){
    $from = $_GET['from'];
    $to = $_GET['to'];
} else {
    $from = $argv[1];
    $to = $argv[2];
}
file_put_contents($to, GrammarCompiler::compile(file_get_contents($from))->serialize());
